package gold.digger;

import java.util.Arrays;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC16 {
    public int threeSumClosest(int[] nums, int target) {
        if (nums.length <= 3) {
            int sum = 0;
            for (int i = 0; i < nums.length; ++i) {
                sum += nums[i];
            }
            return sum;
        }


        Arrays.sort(nums);
        int curClosest = Integer.MAX_VALUE;
        int resultSum = 0;
        for (int i = 0; i < nums.length - 2; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int curMargin = findClosetTwoSum(nums, i + 1, nums.length - 1, target - nums[i]);
            if (Math.abs(curMargin) < curClosest) {
                curClosest = Math.abs(curMargin);
                resultSum = target - curMargin;
            }
        }

        return resultSum;
    }

    public int findClosetTwoSum(int[] nums, int lb, int ub, int target) {
        int curClosest = target - nums[lb] - nums[ub];
        int i = lb, j = ub;
        while (i < j) {
            int curMinus = target - nums[i] - nums[j];
            if (curMinus == 0) {
                return 0;
            }

            if (curMinus > 0) {
                ++i;
            } else {
                --j;
            }

            if (i < j && Math.abs(curClosest) > Math.abs(target - nums[i] - nums[j])) {
                curClosest = target - nums[i] - nums[j];
            }
        }
        return curClosest;
    }

    public static void main(String[] args) {
        LC16 an = new LC16();
        int[] nums = {4, 0, 5, -5, 3, 3, 0, -4, -5};
        int target = -2;
        System.out.println(an.threeSumClosest(nums, target));
    }
}
